package quick_sort

import (
	"learning/gooop/sorting"
)

type tQuickSort struct {
}

func newQuickSort() sorting.ISorter {
	return &tQuickSort{}
}

func (me *tQuickSort) Sort(data []interface{}, comparator sorting.CompareFunction) []interface{} {
	if data == nil {
		return nil
	}

	size := len(data)
	if size <= 1 {
		return data
	}

	if size == 2 {
		if comparator(data[0], data[1]) == sorting.GREATER {
			data[0],data[1] = data[1], data[0]
			return data
		}
	}

	stack := newQStack()
	stack.push(0, size - 1)
	me.qsort(data, comparator, stack)
	return data
}

func (me *tQuickSort) qsort(data []interface{}, comparator sorting.CompareFunction, stack *tQStack) {
	for ;stack.isNotEmpty(); {
		left, right := stack.pop()
		lfrom, lto, rfrom, rto := me.split(data, comparator, left, right)

		if lfrom < lto {
			stack.push(lfrom, lto)
		}
		if rfrom < rto  {
			stack.push(rfrom, rto)
		}
	}
}

func (me *tQuickSort) split(data []interface{}, comparator sorting.CompareFunction, left int, right int) (lfrom, lto, rfrom, rto int) {
	if left >= right {
		return
	}

	v := data[left]
	l := left
	r := right
	rside := true

	for {
		hit := false
		if rside {
			for ; r > l; r-- {
				if comparator(data[r], v) == sorting.LESS {
					hit = true
					break
				}
			}

			if hit {
				data[l], data[r] = data[r], nil
				l++
				rside = false
			}
		} else {
			for ; l < r;l++ {
				if comparator(data[l], v) == sorting.GREATER {
					hit = true
					break
				}
			}

			if hit {
				data[r], data[l] = data[l], nil
				r--
				rside = true
			}
		}

		if l == r {
			data[l] = v
			break
		}
	}

	return left, l - 1, r + 1, right
}

var QuickSorter = newQuickSort()